class Solution {
public:
    int rob(vector<int>& nums) 
    {
        if(nums.size() == 1)
            return nums[0];

        if(nums.size() == 2)
            return max(nums[0], nums[1]);

        vector<int> sum(nums.size() + 1, 0);

        for(int i = 2; i <= nums.size(); i++)
        {
            sum[0] = 0;
            sum[1] = nums[0];

            sum[i] = max(sum[i - 1], sum[i - 2] + nums[i - 1]);
        }

        return sum[nums.size()];
    }
};

//动态规划，到达第i家道歉金额的最大数 = max（前i-1家所得金额，前i-2家所得金额 + 第i家收益）